// KMP
// https://www.luogu.com.cn/problem/P3375
char str[maxn], sub[maxn];
int pi[maxn];

void get_pi(char *s, int len, int *pi) { // 计算字符串 s 的前缀函数，存储到 pi 中
    for (int i = 1; i < len; ++i) {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j]) {
            j = pi[j - 1]; // 寻找下一长度
        }
        if (s[i] == s[j]) ++j; // 如果匹配
        pi[i] = j;
    }
}

int main() {
    scanf("%s%s", str, sub);
    int len = strlen(sub);
    get_pi(sub, len, pi);
    int j = 0; // 失配指针
    for (int i = 0, ed = strlen(str); i < ed; ++i) {
        while (j > 0 && str[i] != sub[j]) // 匹配失败，j 不断倒退
            j = pi[j - 1];
        if (str[i] == sub[j]) ++j; // 该位置匹配成功
        if (j == len) printf("%d\n", i - len + 2); // sub[j] 为 '\0'，肯定不匹配，不需特别处理
    }
    for (int i = 0; i < len; ++i) {
        printf("%d ", pi[i]);
    }
}
